/* ***************************************
 * 二分探索木BSTを構成するクラスファイル
 * *************************************** */
using namespace std;
#define     LEFT    0
#define     RIGHT   1

class node {
    public:
        int     key;        // 点に格納する整数値データ
        node*   parent;     // その点の親を指すポインタ
        node*   left;       // その点の左の子を指すポインタ
        node*   right;      // その点の右の子を指すポインタ
        int     color;      // 赤黒木における赤or黒の情報

    public:
        node() {
            color = 0;      // RED
            left = NULL;
            right = NULL;
        }
};

/* ***************************************
 * 二分探索木を表すクラス
 * *************************************** */
class BST {
    public:
        node*   root;       // 二分探索木の根を格納
        node*   NIL;        // 二分探索木におけるNIL点
        int     count;      // 二分木に格納されている点の数を格納

    public:
        /*
         * デフォルト・コンストラクタ
         * 根をNULL、countを0に初期化する。
         */
        BST() {
            this->NIL = new node();
            this->root = NIL;
            this->NIL->parent = NULL;
            this->NIL->key = 0;
            this->count = 0;
        }


        /*
         * 指定された値をkeyに持つ点を探索する。
         * もし見つかれば1を、見つからなければ0を返す。
         */
        int search( int key ) {
            if( this->place( key ) != NIL ) {
                return 1;
            } else {
                return 0;
            }
        }

        /*
         * 指定された値をkeyとして持つ点を削除する
         * 削除する点が存在しなかったときは0を、
         * 削除する点が存在し、削除できたときは1を返す。
         */
        node* remove( int key ) {
            node*       z_point;    // 削除するノードへのポインタ
            node*       y_point;
            node*       x_point;

            z_point = this->place( key );

            if( z_point == NIL ) {
                // 削除するノードが見つからないときは、
                // ０を返して終了。
                return NULL;
            }

            /*
             * 削除するノードが存在するとき。
             */
            // zが1つ以下の子を持つなら、yをzにする。そうでなければ、zの次節点をyとする。
            if( z_point->left == NIL || z_point->right == NIL ) {
                y_point = z_point;
            } else {
                y_point = this->next( z_point );
            }

            // xをyの子とする。
            if( y_point->left != NIL ) {
                x_point = y_point->left;
            } else {
                x_point = y_point->right;
            }

            // xの親をyの親にする（ポインタの付け替え）
            // xがNILであっても同様にすることで、NILから今辿ってきた親を辿れる。
            x_point->parent = y_point->parent;

            // yが根ならば、xを二分木の根にする。
            // yの親の子ポインタをxを指すようにする。
            if( y_point == root ) {
                this->root = x_point;
            } else if( y_point->parent->left == y_point ) {
                y_point->parent->left = x_point;
            } else {
                y_point->parent->right = x_point;
            }

            // y!=zなら、yの値をzにコピーする。
            if( y_point != z_point ) {
                z_point->key = y_point->key;
            }
            count--;
            return y_point;
        }

        node* insert( int key ) {
            // 木が空のとき
            if( root==NIL ) {
                this->root = new node();
                root->left = NIL;
                root->right = NIL;
                root->parent = NULL;
                root->key = key;
                count ++;
                return root;
            }

            // place関数により、挿入すべき場所を探索
            node*       point = this->place( key );

            // すでに挿入しようとしているデータが存在するときはそのまま終了
            if( point != NIL ) {
                return NULL;
            }

            node    *p = new node();    // 新しく挿入する点のインスタンスを生成
            p->key = key;
            p->left = NIL;
            p->right = NIL;

            p->parent = point->parent;
            if( key < p->parent->key ) {
                p->parent->left = p;
            } else {
                p->parent->right = p;
            }

            this->count ++;             // BSTに格納されている点の数を1増やす

            return p;                   // 今挿入した点のアドレスを返す
        }

        /*
         * 二分探索木上の指定した点から、中間順でラベル付けを
         * 行い、順に出力する。
         */
        void inorder( node* point ) {
            if( point != NIL ) {
                this->inorder( point->left );
                cout << point->key << ":" << point->color << " ";
                this->inorder( point->right );
            }
        }

        /*
         * 二分木全体を中間順で出力する。
         */
        void inorder() {
            this->inorder( this->root );
            cout << "\n";
        }

    protected:
        node* uncle(node* point){
            if( point->parent == NULL ) {
                return NULL;
            }
            return sibling( point->parent );
        }


        node* mini(node* point){
            while(point->left!=NIL){
                point = point->left;
            }
            return point;
        }


        node* next(node* point){
            node*   y;
            if( point->right != NIL )
                return mini( point->right );
            y = point->parent;
            while( y!=NIL && point==y->right ) {
                point = y;
                y = y->parent;
            }
            return y;
        }


        /*
         * 値keyを持つ点を指すポインタを返す。
         * もしそのような点が存在しなければNILを返す。
         * NILを返す際、NIL->parentには、根から辿ってきたときの
         * NILの親を指すようになっている。
         */
        node* place( int key ) {
            node*   point = root;
            while(point!=NIL && key!=point->key ){
                if( key < point->key ){
                    point->left->parent = point;    // yamada change
                    point = point->left;
                } else {
                    point->right->parent = point;    // yamada change
                    point = point->right;
                }
            }
            return point;
        }

        /*
         * 指定された点の兄弟を指すポインタを返す
         */
        node *sibling( node *point ) {
            if( point->parent == NULL ) {
                return NULL;
            }
            if( point->parent->left == point ) {
                return point->parent->right;
            } else {
                return point->parent->left;
            }
        }

        /*
         * 指定した点において、指定方向に回転させる。
         * 成功の場合1を、失敗の場合0を返す。
         * 回転 左：0 　右：1
         */
        void rotation(node* point, int dr){
            node* y;
            if(dr==0){  //左回転
                if(point->right != NIL){  //右の子があるなら
                    y = point->right;
                    point->right = y->left;
                    if(y->left != NIL)
                        y->left->parent = point;
                    y->parent = point->parent;
                    if( point == root ) {
                        this->root = y;
                    } else {
                        if(point == point->parent->left){
                            point->parent->left = y;
                        }else{
                            point->parent->right = y;
                        }
                    }
                    y->left = point;
                    point->parent = y;
                }
            } else {    //右回転
                if(point->left != NIL){  //左の子があるなら
                    y = point->left;
                    point->left = y->right;
                    if(y->right != NIL)
                        y->right->parent = point;
                    y->parent = point->parent;
                    if( point == root ) {  //根で回転の場合
                        this->root = y;
                    }else{
                        if(point == point->parent->left){
                            point->parent->left = y;
                        } else {
                            point->parent->right = y;
                        }
                    }
                    y->right = point;
                    point->parent = y;
                }
            }
        }

        /*
         * 指定した点と、その親、祖父の3点からなるパスを
         * siblingパスに変形させる。
         * 成功すれば、真ん中点のポインタ、失敗すればNULLを返す。
         */
        node* ToSiblingPath( node* point){
            node* a = point->parent;           //pointの親
            if( a == NULL ) {
                return NULL;
            }
            node* y = point->parent->parent;        //pointの祖父
            if(a==NULL || y==NULL){
                //親または祖父が存在しないときは、
                //NULLを返して終了。
                return NULL;
            }
            node*	p = a;
            if(a == y->right){
                if(point == a->left){
                    rotation(a,1);
                    p = point;
                }
                rotation(y,0);
            } else {
                if(point == a->right){
                    rotation(a,0);
                    p = point;
                }
                rotation(y,1);
            }
            return p;
        }


    public:
        void echo() {
            cout << root->key << ":" << root->color << "\n";

            // レベル１の出力
            cout << root->left->key << ":" << root->left->color;
            cout << "        ";
            cout << root->right->key << ":" << root->right->color << "\n";

            // レベル２の出力
            if( root->left->left != NIL ) {
                cout << root->left->left->key << ":" << root->left->left->color << "  ";
            } else {
                cout << "      ";
            }
            if( root->left->right != NIL ) {
                cout << root->left->right->key << ":" << root->left->right->color << "   ";
            } else {
                cout << "      ";
            }
            if( root->right->left != NIL ) {
                cout << root->right->left->key << ":" << root->right->left->color << "  ";
            } else {
                cout << "      ";
            }
            if( root->right->right != NIL ) {
                cout << root->right->right->key << ":" << root->right->right->color << "   ";
            } else {
                cout << "      ";
            }

            cout << "\n\n";
        }

};

